#合并两个有序链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def list_to_linkedlist(lst):
    if not lst:
        return None
    head = ListNode(lst[0])
    current = head
    for val in lst[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def linkedlist_to_list(head):
    lst = []
    current = head
    while current:
        lst.append(current.val)
        current = current.next
    return lst


class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next

        # 处理剩余部分
        curr.next = list1 if list1 else list2
        return dummy.next


if __name__ == "__main__":
    solution = Solution()

    # 示例1
    l1 = list_to_linkedlist([1, 2, 4])
    l2 = list_to_linkedlist([1, 3, 4])
    merged = solution.mergeTwoLists(l1, l2)
    print("示例1 输出:", linkedlist_to_list(merged))  # [1,1,2,3,4,4]

    # 示例2
    l1 = list_to_linkedlist([])
    l2 = list_to_linkedlist([])
    merged = solution.mergeTwoLists(l1, l2)
    print("示例2 输出:", linkedlist_to_list(merged))  # []

    # 示例3
    l1 = list_to_linkedlist([])
    l2 = list_to_linkedlist([0])
    merged = solution.mergeTwoLists(l1, l2)
    print("示例3 输出:", linkedlist_to_list(merged))  # [0]